`
https://leetcode.cn/problems/count-the-number-of-fair-pairs/
`

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countFairPairs = function (nums, lower, upper) {
  nums.sort((a, b) => a - b)
  let res = 0
  for (let j = 0; j < nums.length; j++) {
    // lower − nums[j] <= nums[i] <= upper − nums[j]
    // 在 [0, j - 1] 中二分
    const l = lower_bound(nums, j, lower - nums[j])
    const r = lower_bound(nums, j, upper - nums[j] + 1)
    res += r - l
  }
  return res
};

function lower_bound(arr, right, target) {
  let left = -1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (arr[mid] < target) {
      left = mid
    } else {
      right = mid
    }
  }
  return left
}